package cn.Leecode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.LinkedList;

/*
@李子宁
Happy,happy everyday!
冲鸭！
2021/3/1

*/
public class Soution {

    public static void main(String[] args) {
        Soution S = new Soution();
        System.out.println(S.longestPalindromeSubseq("bbbab"));
    }

    public int longestPalindromeSubseq(String s) {
        int len = s.length();
        int [][] dp = new int[len][len];
        for(int i = len - 1; i>=0; i--){
            dp[i][i] = 1;
            for(int j = i+1; j < len; j++){
                if(s.charAt(i) == s.charAt(j))
                    dp[i][j] = dp[i+1][j-1] + 2;
                else
                    dp[i][j] = Math.max(dp[i+1][j], dp[i][j-1]);
            }
        }
        return dp[0][len-1];
    }

    public int getChange(int num){
        try {
           // num = 4;
            return num;
        }finally {
            num = 5;
            //return num;
        }
    }

    public int[] printNumbers(int n) {
        int nums = 1;
        for (int i = 0; i < n; i++) {
            nums += 9*Math.pow(10,i);
        }

        int size = nums-1;
        int[] res = new int[size];
        for(int i = 0; i < size; i++){
            res[i] = i + 1;
        }
        return res;
    }

    public double myPow(double x, int n) {
        double res = 1.0;
        if(x == 1) return x;
        long b = n;
        long tmp =  b >= 0 ? b : -b;
        for(int i = 0;i <tmp; i ++){
            res *= x;
        }
        return b >= 0 ? res : 1/res;
    }
}
